Myönteisen päätöksen saanut Kolumbus lähti Granadasta toukokuussa 1492 ja matkusti satamakaupunki Palosiin. Siellä hän sai kaupungilta sopimuksensa mukaisesti käyttöönsä kaksi karavelia, Pintan ja Niñan, joiden miehistölle valtio maksoi etukäteen neljän kuukauden palkan. Lippulaivakseen Kolumbus sai Santa María -nimisen aluksen. Laivat olivat lähtövalmiit kymmenen viikon kuluttua.[16] Matkan järjestelyissä ja miehistön hankinnassa tärkeässä osassa olivat Pinzónin veljekset.[17] Kolmella laivalla matkaan lähti yhteensä 90 miestä, joista 86 oli espanjalaisia. Kolumbuksen osuus matkan kustannuksista oli ehkä kahdeksasosa, minkä hän oli lainannut.[18]